package linkedList;

public class JosephusSingleListedDemo {
    public static void main(String[] args) {
        JosephusSingleListed josephusSingleListed = new JosephusSingleListed();
        josephusSingleListed.add(5);
        josephusSingleListed.list();
        josephusSingleListed.delete(3);

    }
}

class JosephusSingleListed {
    private Boy first;//这是约瑟夫环的一个节点 默认为null

    public Boy getFirst() {
        return first;
    }

    public void setFirst(Boy first) {
        this.first = first;
    }

    //添加节点
    public void add(int nums) {
        if (nums < 2) {
            System.out.println("节点数不能小于2");
            return;
        }
        //创建当前节点
        Boy curBoy = null;
        for (int i = 1; i <= nums; i++) {
            if (i == 1) {
                first = new Boy(i);
                first.next = first;
                curBoy = first;
            } else {
                curBoy.next = new Boy(i);
                curBoy = curBoy.next;
                curBoy.next = first;
            }
        }
    }

    //遍历节点
    public void list() {
        if (first == null) {
            //说明是个空的约瑟夫环
            System.out.println("约瑟夫环为空");
            return;
        }
        //使用一个临时变量
        Boy curBoy = first;
        while (true) {
            System.out.println(curBoy);
            if (curBoy.next == first) {
                //已经遍历一圈
                break;
            }
            curBoy = curBoy.next;
        }
    }

    public void delete(int m) {
        if (first == null) {
            System.out.println("约瑟夫环为空");
            return;
        }
        int length = getLength();
        if (m > length || m < 1) {
            System.out.println("m值不合法");
            return;
        }
        //正式开始出圈
        Boy curBoy = first;
        //curBoy.next = first;
        //先让curBoy指向first的后一个
        while (true) {
            if (curBoy.next == first) {
                break;
            }
            curBoy = curBoy.next;
        }
        while (true) {
            if (length == 1) {
                //说明只有一个节点
                //System.out.println("出圈的节点no为：" + first.no);
                System.out.println("约瑟夫环只有一个节点,删除的节点为+" + first.no);
                first = null;
                break;
            }

            for (int i = 0; i < m - 1; i++) {
                first = first.next;
                curBoy = curBoy.next;
            }
            curBoy.next = first.next;
            System.out.println("出圈的节点no为：" + first.no);
            if (first.next == first) {
                break;
            }
            first = first.next;

        }


    }

    //获取约瑟夫环的长度
    public int getLength() {
        if (first == null) {
            //说明是个空的约瑟夫环
            System.out.println("约瑟夫环为空");
            return 0;
        }
        int length = 0;
        //使用一个临时变量
        Boy curBoy = first;
        while (true) {
            length++;
            if (curBoy.next == first) {
                //已经遍历一圈
                break;
            }
            curBoy = curBoy.next;
        }
        return length;
    }
}

class Boy {
    public int no;//编号
    public Boy next;//指向下一个节点

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}
